package chapter03;

import java.util.List;

public class MinimumTotal120 {
    /**
     * 记忆化搜索
     * process(triangle,row,col,length)
     * 从triangle[row,col]尝试以它开头最小路径和
     * length代表行数
     * 递归出口
     *  1).来到最后一行 row==length
     *      return 0
     *  2).来到最后一列 ol==triangle.get(row).size()
     *      说明本行没有结果 这种搜索无效
     *      return Max_value
     *  3.尝试下方和右下角，选择最小值返回
     *      return path.get(col)+Math.min(process(triangle,row+1,col,length),process(triangle,row+1,col+1,length));
     *  为了减少重复搜索 增加缓存dp[row][col] 但是最后一个测试点仍超时 改为动态规划O(N^2)
     */
    public int minimumTotal(List<List<Integer>> triangle){
        int length=triangle.size();
        int[][] dp=new int[length+1][length+1];
        for(int j=0;j<=length;j++){
            dp[length][j]=0;
        }
        for(int i=0;i<length;i++){
            dp[i][i+1]=Integer.MAX_VALUE;
        }
        for(int i=length-1;i>=0;i--){
            for(int j=i;j>=0;j--){
                dp[i][j]=triangle.get(i).get(j)+Math.min(dp[i+1][j],dp[i+1][j+1]);
            }
        }
        return dp[0][0];
    }

    public int minimumTotal1(List<List<Integer>> triangle) {
        int length=triangle.size();
        int[][] dp=new int[length+1][length+1];
        return process(triangle,0,0,length,dp);
    }

    public int process(List<List<Integer>> triangle,int row ,int col,int length,int[][] dp){
        if(dp[row][col]!=0){
            return dp[row][col];
        }
        if(row==length){
            dp[row][col]=0;
            return 0;
        }
        List<Integer> path=triangle.get(row);
        if(col==path.size()){
            dp[row][col]=Integer.MAX_VALUE;
            return Integer.MAX_VALUE;
        }
        dp[row][col]=path.get(col)+Math.min(process(triangle,row+1,col,length,dp),process(triangle,row+1,col+1,length,dp));
        return dp[row][col];
    }
}
